package com.yeung.swordoffer;

import java.util.*;

public class 字符串的全排列 {
    public static void main(String[] args) {
        ArrayList<String> strings = Permutation("123");
        for (String string : strings) {
            System.out.println(string);
        }
    }

    /**
     * 利用set来去重
     * <p>
     * 思想:
     * 比如123
     * 拿么先去1, 则接下来取2或者3,
     * 取了2, 最后一次只能取3 ->123
     * 取了3, 最后依次只能取2 ->132
     * 如第一次取得不是1,是2
     * 那么重复上面的流程
     *
     * @param str
     * @return
     */
    public static ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        if (str.equals("") || str == null) return result;
        Set<String> set = new LinkedHashSet<>();
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        boolean[] vis = new boolean[chars.length];
        char[] tmp = new char[chars.length];
        permutation(0, tmp, chars, vis, set);
        result.addAll(set);
        return result;

    }

    /**
     * dfs形式遍历字符数组
     * * 利用访问数组来确定某一位置的元素是否已经访问
     * <p>
     *
     * @param index
     * @param tmp
     * @param chars
     * @param vis
     * @param set
     */
    public static void permutation(int index, char[] tmp, char[] chars, boolean[] vis, Set<String> set) {
        if (index == chars.length) {
            set.add(new String(tmp));
            return;
        }
        //每一轮选一个不同的字符(下一轮选剩下的)来进行全排列
        for (int i = 0; i < chars.length; i++) {
            if (!vis[i]) {
                tmp[index] = chars[i];
                vis[i] = true;
                permutation(index + 1, tmp, chars, vis, set);
                //回溯
                vis[i] = false;
            }
        }
    }

    /**
     * 第二种全排列思路
     *
     * @param str
     * @return
     */
    public static ArrayList<String> Permutation2(String str) {
        ArrayList<String> result = new ArrayList<>();
        if (str == null || str.equals("")) {
            return result;
        }
        char[] chars = str.toCharArray();
        Set<String> set = new TreeSet<>();
        permutation2(0, chars, set);
        result.addAll(set);
        return result;
    }

    public static void permutation2(int index, char[] chars, Set<String> set) {
        if (index == chars.length - 1) {
            set.add(new String(chars));
            return;
        }
        //固定子序列的第一个, 后面的子序列右按照这个流程进行交换排列
        for (int i = index; i < chars.length; i++) {
            swap(chars, index, i);
            permutation2(index + 1, chars, set);
            swap(chars, index, i);
        }
    }

    public static void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }

    //-----------方法四  字典序算法---------
    public static ArrayList<String> Permutation4(String str) {
        ArrayList<String> result = new ArrayList<>();
        if (str != null && str.length() > 0) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            result.add(new String(chars));
            while (true) {
                int firstPositiveOrder = chars.length - 2;
                //对当前数列中从后往前找到第一个正序对，并记录该正序对位置A(是一个拐点,后边的值都小于拐点)

                while (firstPositiveOrder >= 0
                        && chars[firstPositiveOrder] >= chars[firstPositiveOrder + 1]) {
                    firstPositiveOrder--;
                }
                //如果firstPositiveOrder=-1 则整个序列都查完了一遍, 且整个序列是递减的,终止
                if (firstPositiveOrder == -1) {
                    break;
                }
                int index = chars.length - 1;//序列中额最后一个
                //从后往前找第一个大于拐点处数的下标
                while (chars[index] <= chars[firstPositiveOrder]) {
                    index--;
                }
                swap(chars, firstPositiveOrder, index);
                reverse(chars, firstPositiveOrder + 1, chars.length);
                result.add(new String(chars));
            }
        }
        return result;
    }

    public static void reverse(char[] chars, int begin, int end) {
        for (int i = begin, j = end - 1; i < j; i++, j--) {
            swap(chars, i, j);
        }
    }

}
